package airthmetic.exercise.sort.cmp;


import java.util.Random;

// 堆排序
public class _912_排序数组_Heap {

    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length < 2) {
            return nums;
        }
        int end = nums.length - 1;
        buildHeap(nums, end);

        for (int i = end; i >= 1; i--) {
            swap(nums, 0, i);
            end--;
            down(nums, 0, end);
        }

        return nums;
    }

    public void buildHeap(int[] nums, int end) {
        for (int i = (end - 1) >> 1; i >= 0; i--) {
            down(nums, i, end);
        }
    }

    public void down(int[] nums, int start, int end) {
        while (start <= (end - 1) >> 1) {
            int left = (start << 1) + 1;
            int right = left + 1;

            int large = start;
            if (left <= end && nums[left] > nums[large]) {
                large = left;
            }
            if (right <= end && nums[right] > nums[large]) {
                large = right;
            }

            if (large != start) {
                swap(nums, start, large);
                start = large;
            }else{
                break;
            }
        }


    }

    public void swap(int[] nums, int i, int j) {
        if (i == j) {
            return;
        }
        nums[i] ^= nums[j];
        nums[j] ^= nums[i];
        nums[i] ^= nums[j];
    }


    public static void main(String[] args) {
        _912_排序数组_Heap heap = new _912_排序数组_Heap();
        int[] nums = {7,9,4,1,5,3};
        heap.sortArray(nums);
        for (int num : nums) {
            System.out.println(num);
        }
    }
}
